package basic.study.leetcode;

import java.util.Stack;

/**
 * @ClassName Hard42
 * @Description 接雨水
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/20 9:47
 * @Version 1.0
 */
public class Hard42 {
    class Solution {
        /**
         * 当前行
         * @param height
         * @return
         */
        public int trap(int[] height) {
            int sum = 0;
            int max = getMax(height);//找到最大的高度，以便遍历
            for (int i = 1; i <= max; i++) {
                boolean isStart = false;//标记是否开始更新temp
                int temp_sum = 0;
                for (int j = 0; j < height.length; j++) {
                    if (isStart && height[j] < i) {
                        temp_sum++;
                    }
                    if (height[j] >= i) {
                        sum += temp_sum;
                        temp_sum = 0;
                        isStart = true;
                    }
                }
            }
            return sum;
        }

        private int getMax(int[] height) {
            int max = 0;
            for (int i = 0; i < height.length; i++) {
                if (height[i] > max) {
                    max = height[i];
                }
            }
            return max;
        }
    }

    class Solution1 {
        /**
         * 当前列
         * @param height
         * @return
         */
        public int trap(int[] height) {
            int sum = 0;
            //最两端不用考虑，因为一定不会有水，所以下标从1到length-2
            for (int i = 1; i < height.length-1; i++) {
                int max_left = 0;
                //找出左边最高
                for (int j = i-1; j >= 0; j--) {
                    if (height[j] > max_left) {
                        max_left = height[j];
                    }
                }
                int max_right = 0;
                for (int j = i+1; j < height.length; j++) {
                    if (height[j] > max_right) {
                        max_right = height[j];
                    }
                }
                //找出两端最小的
                int min = Math.min(max_left, max_right);
                //只有较小的一段大于当前列的高度才会有水
                if (min > height[i]) {
                    sum = sum + (min - height[i]);
                }
            }
            return sum;
        }
    }

    class Solution2 {
        /**
         * 动态规划
         * @param height
         * @return
         */
        public int trap(int[] height) {
            int sum = 0;
            int[] max_left = new int[height.length];
            int[] max_right = new int[height.length];

            for (int i = 1; i < height.length-1; i++) {
                max_left[i] = Math.max(max_left[i-1], height[i-1]);
            }
            for (int i = height.length-2; i >= 0; i--) {
                max_right[i] = Math.max(max_right[i+1], height[i+1]);
            }
            for (int i = 1; i < height.length-1; i++) {
                int min = Math.max(max_left[i], max_right[i]);
                if (min > height[i]) {
                    sum += (min - height[i]);
                }
            }
            return sum;
        }
    }

    class Solution3 {
        public int trap(int[] height) {
            int sum = 0;
            Stack<Integer> stack = new Stack<>();
            int current = 0;
            while (current < height.length) {
                //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
                while (!stack.empty() && height[current] > height[stack.peek()]) {
                    int h = height[stack.peek()]; //取出要出栈的元素
                    stack.pop(); //出栈
                    if (stack.empty()) { // 栈空就出去
                        break;
                    }
                    int distance = current - stack.peek() - 1; //两堵墙之前的距离。
                    int min = Math.min(height[stack.peek()], height[current]);
                    sum = sum + distance * (min - h);
                }
                stack.push(current); //当前指向的墙入栈
                current++; //指针后移
            }
            return sum;
        }

    }
}
